package stru1.day10;

import java.util.LinkedList;
import java.util.List;

/**
 * 94. 二叉树的中序遍历
 */
public class Solution2 {
    public static void main(String[] args) {
        System.out.println(inorderTraversal(new TreeNode(1, null, new TreeNode(2, new TreeNode(3), null))));
        System.out.println(inorderTraversal(null));
        System.out.println(inorderTraversal(new TreeNode(1)));
    }

    /**
     * 递归
     * 另两种解法为：利用栈迭代和 Morris中序遍历
     */
    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new LinkedList<>();
        inorder(ans, root);
        return ans;
    }

    private static void inorder(List<Integer> ans, TreeNode node) {
        if (node == null) return;
        inorder(ans, node.left);
        ans.add(node.val);
        inorder(ans, node.right);
    }
}
